{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# no_wait_baking_scheduling_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/examples/no_wait_baking_scheduling_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/python/no_wait_baking_scheduling_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Scheduling cooking tasks in a bakery using no-wait jobshop scheduling.\n",
    "\n",
    "We are scheduling a full day of baking:\n",
    "  - Work starts at 4am.\n",
    "  - The shop closes at 10PM.\n",
    "  - Durations are in minutes. Time starts at midnight.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "from typing import List, Sequence, Tuple\n",
    "\n",
    "from ortools.sat.colab import flags\n",
    "from google.protobuf import text_format\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "_PARAMS = flags.define_string(\n",
    "    \"params\",\n",
    "    \"num_search_workers:16, max_time_in_seconds:30\",\n",
    "    \"Sat solver parameters.\",\n",
    ")\n",
    "\n",
    "# Recipes\n",
    "CROISSANT = \"croissant\"\n",
    "APPLE_PIE = \"apple pie\"\n",
    "BRIOCHE = \"brioche\"\n",
    "CHOCOLATE_CAKE = \"chocolate cake\"\n",
    "\n",
    "# Skills\n",
    "BAKING = \"baking\"\n",
    "PROOFING = \"proofing\"\n",
    "COOKING = \"cooking\"\n",
    "COOLING = \"cooling\"\n",
    "DECORATING = \"decorating\"\n",
    "DISPLAY = \"display\"\n",
    "\n",
    "\n",
    "class Task:\n",
    "    \"\"\"A unit baking task.\n",
    "\n",
    "    - Simple baking tasks have a fixed duration. They are performed by workers.\n",
    "    - Waiting/cooling/proofing tasks have a min and a max duration.\n",
    "      They are performed by machine or they use space resources.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, name, min_duration, max_duration):\n",
    "        self.name = name\n",
    "        self.min_duration = min_duration\n",
    "        self.max_duration = max_duration\n",
    "\n",
    "\n",
    "class Skill:\n",
    "    \"\"\"The skill of a worker or the capability of a machine.\"\"\"\n",
    "\n",
    "    def __init__(self, name, efficiency):\n",
    "        self.name = name\n",
    "        # Efficiency is currently not used.\n",
    "        self.efficiency = efficiency\n",
    "\n",
    "\n",
    "class Recipe:\n",
    "    \"\"\"A recipe is a sequence of cooking tasks.\"\"\"\n",
    "\n",
    "    def __init__(self, name):\n",
    "        self.name = name\n",
    "        self.tasks = []\n",
    "\n",
    "    def add_task(\n",
    "        self, resource_name: str, min_duration: int, max_duration: int\n",
    "    ) -> \"Recipe\":\n",
    "        self.tasks.append(Task(resource_name, min_duration, max_duration))\n",
    "        return self\n",
    "\n",
    "\n",
    "class Resource:\n",
    "    \"\"\"A resource is a worker, a machine, or just some space for cakes to rest.\n",
    "\n",
    "    - Workers have a capacity of 1 and can have variable efficiency.\n",
    "    - Machines and spaces have a capacity greater or equal to one, but the\n",
    "      efficiency is fixed to 100.\n",
    "\n",
    "      For a worker with efficiency k and a task of duration t, the resulting\n",
    "      work will have a duration `ceil(t * k)`.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, name, capacity):\n",
    "        self.name = name\n",
    "        self.capacity = capacity\n",
    "        self.skills = []\n",
    "\n",
    "    def add_skill(self, skill_name: str, efficiency: float) -> \"Resource\":\n",
    "        self.skills.append(Skill(skill_name, efficiency))\n",
    "        return self\n",
    "\n",
    "\n",
    "class Order:\n",
    "    \"\"\"An order is a recipe that should be delivered at a given due date.\"\"\"\n",
    "\n",
    "    def __init__(self, unique_id, recipe_name, due_date, quantity):\n",
    "        \"\"\"Builds an order.\n",
    "\n",
    "        Args:\n",
    "          unique_id: A unique identifier for the order. Used to display the result.\n",
    "          recipe_name: The name of the recipe. It must match one of the recipes.\n",
    "          due_date: The due date in minutes since midnight.\n",
    "          quantity: How many cakes to prepare.\n",
    "        \"\"\"\n",
    "        self.unique_id = unique_id\n",
    "        self.recipe_name = recipe_name\n",
    "        self.due_date = due_date\n",
    "        self.quantity = quantity\n",
    "\n",
    "\n",
    "def set_up_data() -> Tuple[List[Recipe], List[Resource], List[Order]]:\n",
    "    \"\"\"Set up the bakery problem data.\"\"\"\n",
    "\n",
    "    # Recipes.\n",
    "    croissant_recipe = Recipe(CROISSANT)\n",
    "    croissant_recipe.add_task(BAKING, 15, 15)\n",
    "    croissant_recipe.add_task(PROOFING, 60, 90)\n",
    "    croissant_recipe.add_task(COOKING, 20, 20)\n",
    "    croissant_recipe.add_task(DISPLAY, 5, 5 * 60)\n",
    "\n",
    "    apple_pie_recipe = Recipe(APPLE_PIE)\n",
    "    apple_pie_recipe.add_task(BAKING, 25, 25)\n",
    "    apple_pie_recipe.add_task(PROOFING, 15, 60)\n",
    "    apple_pie_recipe.add_task(COOKING, 30, 30)\n",
    "    apple_pie_recipe.add_task(DECORATING, 5, 5)\n",
    "    apple_pie_recipe.add_task(DISPLAY, 5, 5 * 60)\n",
    "\n",
    "    brioche_recipe = Recipe(BRIOCHE)\n",
    "    brioche_recipe.add_task(BAKING, 20, 20)\n",
    "    brioche_recipe.add_task(PROOFING, 60, 90)\n",
    "    brioche_recipe.add_task(COOKING, 30, 30)\n",
    "    brioche_recipe.add_task(DISPLAY, 5, 5 * 60)\n",
    "\n",
    "    chocolate_cake_recipe = Recipe(CHOCOLATE_CAKE)\n",
    "    chocolate_cake_recipe.add_task(BAKING, 15, 15)\n",
    "    chocolate_cake_recipe.add_task(COOKING, 25, 25)\n",
    "    chocolate_cake_recipe.add_task(DECORATING, 15, 15)\n",
    "    chocolate_cake_recipe.add_task(DISPLAY, 5, 5 * 60)\n",
    "    recipes = [\n",
    "        croissant_recipe,\n",
    "        apple_pie_recipe,\n",
    "        brioche_recipe,\n",
    "        chocolate_cake_recipe,\n",
    "    ]\n",
    "\n",
    "    # Resources.\n",
    "    baker1 = Resource(\"baker1\", 1).add_skill(BAKING, 1.0)\n",
    "    baker2 = Resource(\"baker2\", 1).add_skill(BAKING, 1.0)\n",
    "    decorator1 = Resource(\"decorator1\", 1).add_skill(DECORATING, 1.0)\n",
    "    waiting_space = Resource(\"waiting_space\", 4).add_skill(PROOFING, 1.0)\n",
    "    oven = Resource(\"oven\", 4).add_skill(COOKING, 1.0)\n",
    "    display_space = Resource(\"display_space\", 12).add_skill(DISPLAY, 1.0)\n",
    "    resources = [baker1, baker2, decorator1, waiting_space, oven, display_space]\n",
    "\n",
    "    # Orders\n",
    "    croissant_7am = Order(\"croissant_7am\", CROISSANT, 7 * 60, 3)\n",
    "    croissant_8am = Order(\"croissant_8am\", CROISSANT, 8 * 60, 3)\n",
    "    croissant_9am = Order(\"croissant_9am\", CROISSANT, 9 * 60, 2)\n",
    "    croissant_10am = Order(\"croissant_10am\", CROISSANT, 10 * 60, 1)\n",
    "    croissant_11am = Order(\"croissant_11am\", CROISSANT, 11 * 60, 1)\n",
    "    brioche_10am = Order(\"brioche_10am\", BRIOCHE, 10 * 60, 8)\n",
    "    brioche_12pm = Order(\"brioche_12pm\", BRIOCHE, 12 * 60, 8)\n",
    "    apple_pie_1pm = Order(\"apple_pie_1pm\", APPLE_PIE, 13 * 60, 10)\n",
    "    chocolate_4pm = Order(\"chocolate_4pm\", CHOCOLATE_CAKE, 16 * 60, 10)\n",
    "    orders = [\n",
    "        croissant_7am,\n",
    "        croissant_8am,\n",
    "        croissant_9am,\n",
    "        croissant_10am,\n",
    "        croissant_11am,\n",
    "        brioche_10am,\n",
    "        brioche_12pm,\n",
    "        apple_pie_1pm,\n",
    "        chocolate_4pm,\n",
    "    ]\n",
    "\n",
    "    return recipes, resources, orders\n",
    "\n",
    "\n",
    "def solve_with_cp_sat(\n",
    "    recipes: List[Recipe], resources: List[Resource], orders: List[Order]\n",
    ") -> None:\n",
    "    \"\"\"Build the optimization model, and solve the problem.\"\"\"\n",
    "\n",
    "    model = cp_model.CpModel()\n",
    "    horizon = 22 * 60  # 10PM.\n",
    "    start_work = 4 * 60  # 4am.\n",
    "\n",
    "    # Parse recipes.\n",
    "    recipe_by_name = {}\n",
    "    for recipe in recipes:\n",
    "        recipe_by_name[recipe.name] = recipe\n",
    "\n",
    "    # Parse resources.\n",
    "    resource_by_name = {}\n",
    "    resource_list_by_skill_name = collections.defaultdict(list)\n",
    "    for resource in resources:\n",
    "        resource_by_name[resource.name] = resource\n",
    "        for skill in resource.skills:\n",
    "            resource_list_by_skill_name[skill.name].append(resource)\n",
    "\n",
    "    # Parse orders and create one optional copy per eligible resource and per\n",
    "    # task.\n",
    "    interval_list_by_resource_name = collections.defaultdict(list)\n",
    "    orders_sequence_of_events = collections.defaultdict(list)\n",
    "    sorted_orders = []\n",
    "    tardiness_vars = []\n",
    "    for order in orders:\n",
    "        for batch in range(order.quantity):\n",
    "            order_id = f\"{order.unique_id}_{batch}\"\n",
    "            sorted_orders.append(order_id)\n",
    "            previous_end = None\n",
    "            due_date = order.due_date\n",
    "            recipe = recipe_by_name[order.recipe_name]\n",
    "            for task in recipe.tasks:\n",
    "                skill_name = task.name\n",
    "                suffix = f\"_{order.unique_id}_batch{batch}_{skill_name}\"\n",
    "\n",
    "                if previous_end is None:\n",
    "                    start = model.new_int_var(start_work, horizon, f\"start{suffix}\")\n",
    "                    orders_sequence_of_events[order_id].append(\n",
    "                        (start, f\"start{suffix}\")\n",
    "                    )\n",
    "                else:\n",
    "                    start = previous_end\n",
    "\n",
    "                size = model.new_int_var(\n",
    "                    task.min_duration, task.max_duration, f\"size{suffix}\"\n",
    "                )\n",
    "                if task == recipe.tasks[-1]:\n",
    "                    # The order must end after the due_date. Ideally, exactly at the\n",
    "                    # due_date.\n",
    "                    tardiness = model.new_int_var(0, horizon - due_date, f\"end{suffix}\")\n",
    "                    end = tardiness + due_date\n",
    "\n",
    "                    # Store the end_var for the objective.\n",
    "                    tardiness_vars.append(tardiness)\n",
    "                else:\n",
    "                    end = model.new_int_var(start_work, horizon, f\"end{suffix}\")\n",
    "                orders_sequence_of_events[order_id].append((end, f\"end{suffix}\"))\n",
    "                previous_end = end\n",
    "\n",
    "                # Per resource copy.\n",
    "                presence_literals = []\n",
    "                for resource in resource_list_by_skill_name[skill_name]:\n",
    "                    presence = model.new_bool_var(f\"presence{suffix}_{resource.name}\")\n",
    "                    copy = model.new_optional_interval_var(\n",
    "                        start, size, end, presence, f\"interval{suffix}_{resource.name}\"\n",
    "                    )\n",
    "                    interval_list_by_resource_name[resource.name].append(copy)\n",
    "                    presence_literals.append(presence)\n",
    "\n",
    "                # Only one copy will be performed.\n",
    "                model.add_exactly_one(presence_literals)\n",
    "\n",
    "    # Create resource constraints.\n",
    "    for resource in resources:\n",
    "        intervals = interval_list_by_resource_name[resource.name]\n",
    "        if resource.capacity == 1:\n",
    "            model.add_no_overlap(intervals)\n",
    "        else:\n",
    "            model.add_cumulative(intervals, [1] * len(intervals), resource.capacity)\n",
    "\n",
    "    # The objective is to minimize the sum of the tardiness values of each jobs.\n",
    "    # The tardiness is difference between the end time of an order and its\n",
    "    # due date.\n",
    "    model.minimize(sum(tardiness_vars))\n",
    "\n",
    "    # Solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    if _PARAMS.value:\n",
    "        text_format.Parse(_PARAMS.value, solver.parameters)\n",
    "    solver.parameters.log_search_progress = True\n",
    "    status = solver.solve(model)\n",
    "\n",
    "    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:\n",
    "        for order_id in sorted_orders:\n",
    "            print(f\"{order_id}:\")\n",
    "            for time_expr, event_id in orders_sequence_of_events[order_id]:\n",
    "                time = solver.value(time_expr)\n",
    "                print(f\"  {event_id} at {time // 60}:{time % 60:02}\")\n",
    "\n",
    "\n",
    "def main(argv: Sequence[str]) -> None:\n",
    "    if len(argv) > 1:\n",
    "        raise app.UsageError(\"Too many command-line arguments.\")\n",
    "\n",
    "    recipes, resources, orders = set_up_data()\n",
    "    solve_with_cp_sat(recipes, resources, orders)\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
